//输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 
//
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：6 
//
// 
//
// 限制： 
//
// 
// 1 <= n < 2^31 
// 
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/ 
// Related Topics 递归 数学 动态规划 👍 272 👎 0

package com.cute.leetcode.editor.cn;
public class OneNzhengShuZhong1chuXianDeCiShuLcof {
    public static void main(String[] args) {
        new OneNzhengShuZhong1chuXianDeCiShuLcof().new Solution().countDigitOne(351);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         *
         * 统计1~n之间1出现的次数
         * 最常规的解法就是一个数一个数的统计，时间复杂度NlogN，肯定会超时的
         *
         * 将数字n分为high cur low三部分即左中右
         * cur初始化为第一位，high为左边，low为0
         * 求解时一位一位的求出现次数进行累加
         *
         * case 1: cur=0
         *      2  3   0  4
         *      千位和百位可以选00 01 02....22  十位可以取到1( 形如[00|01..|22]1[0-9] 都是<2304 ) 个位可以选0-9  共有 23 * 10 中排列
         *      当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23，十位只能能取0，个位取0-4即 2300 2301 2302 2303 2304
         *      但是2301不应该算进来，这个1是单独出现在个位的，各位为1的时候2031已经统计过了
         *      即 23*10
         * case 2: cur=1
         *    2  3  1  4
         *    千位和百位可以选00 01 02....22  十位可以取到1 个位可以选0-9  共有 23 * 10 中排列
         *    当千位和百位取23,十位取1，个位可以去0-4 即 2310-2314共5个
         *    即 23 *10 + 4 +1
         * case 3: cur>1 即2-9
         *    2  3  2  4
         *    千位和百位可以选00 01 02....22  十位可以取到1(形如 [00|01...|22]1[0-9] 都是<2324) 个位可以选0-9  共有 23 * 10 中排列
         *    当千位和百位取23,十位取1，个位可以去0-9 即 2310-2319共10个 （其中2311，被计算了两次，此次统计只算一个1，因为个位上已经统计了一次2311）
         *    即 23 *10 + 10
         */
        public int countDigitOne(int n) {
            int digit = 1, res = 0;
            int high = n / 10, cur = n % 10, low = 0;// 初始化三部分
            while (high != 0 || cur != 0){
                if (cur == 0) res += high * digit;// cur为0时只与高位有关
                else if (cur == 1) res += high * digit + low + 1;// 为1时与高低位都有关
                else res += (high + 1) * digit;// 2-9的时候需要将高位+1
                // 各个部分进行更新
                low += cur * digit;
                cur = high % 10;
                high /= 10;
                digit *= 10;
            }
            return res;
        }

        /**
         * 统计1-n中数字k出现的次数
         */
        public int countDigitOne(int n, int k) {
            int digit = 1, res = 0;
            int high = n / 10, cur = n % 10, low = 0;
            while (high != 0 || (cur != 0 && k != 0)){
                if (cur < k) res += high * digit;
                else if (cur == k) res += (high - k == 0 ? 1 : 0) * digit + low + 1;
                else res += (high + k == 0 ? 0 : 1) * digit;
                low += cur * digit;
                cur = high % 10;
                high /= 10;
                digit *= 10;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}